package com.lfs.dp;

/*
    爬楼梯12
 */
public class ClimbStairs70 {
    /*
      确定dp数组（dp table）以及下标的含义:  第i个台阶有dp[i]种方法
      这题与509斐波那契数列并不完全相同,当台阶为0时没有方法才对,也就是不考虑台阶为0时的情况,也就不考虑索引为0的情况,
      因此,我们在初始化时要从索引1 2时开始初始化,for循环也因此要从3开始计算(1+2)

      这里和509一样存在着初始化 数组索引越界的问题 这里再说明一次:
      因为我们初始化所需要的最大数组长度为3 dp[2] = 2 索引 0 1 2  dp.length = 3
      但我们创建数组时默认给的长度是[n+1] ,这就有漏洞,当n=1时,我们只会创建一个长度为2的dp数组,但我们初始化时需要的最小长度数组为3,此时
      初始化dp[2] = 2时dp数组索引越界

      解决本法:(本题采用第一种方式)
      第一种方式: if (n <= 2) return n;
      第二种方式: int[] dp = new int[n + 2];
      */
    /*
        为什么爬楼梯的方法会是前两次方法之和? 与斐波那契数列一样?
        楼梯阶数    跳法  1 2 3 5
            1       (1)
            2       (1,1)(2)
            3       (1,1,1)(1,2)(2,1)
            4       (1,1,1,1)(1,2,1)(2,1,1)
                    (1,1,2)(2,2)

         我们以第4阶为例, 第一行3种跳法,其实是第三种跳法上多跳一个台阶
                        第二行2中跳法,其实是第二种跳法伤一次多跳两个台阶
         这样一看,4阶台阶时跳法总和其实是 2阶跳法+3阶跳法 = 4阶跳法

     */
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
